/**
 * 不同的子序列 子序列出现的次数
 * 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 7 取模
输入：s = "rabbbit", t = "rabbit"
输出：3
 */
/**
 * dp[i][j] s[i-1]结尾 可以组成t[j-1]结尾的个数
 * 判断新元素的时候
 * 1 当前元素相同 s[i-1]=t[j-1];
 * 1-1 （完全新元素） 用s[i-1]结尾来匹配：dp[i-1][j-1] =之前累积的次数
 * 1-2 （新元素之前累积过 ）不用用s[i-1]来匹配：dp[i-1][j]
 * dp[i][j] = dp[i-1][j-1](没加上当前元素-出现的次数) + dp[i-1][j]
 * 2当前元素不同； 不用用s[i-1]来匹配：dp[i-1][j]
 * 【初始化】
 * s=0 dp[0][j]=0 无法组成t
 * t=0 dp[i][0]=1
 */
var numDistinct = function(s, t) {
   const [m,n] = [s.length, t.length];
   const dp = Array(m+1).fill().map(() => Array(n+1).fill(0));
   for(let i=0;i<=m;i++) {
    dp[i][0]=1;
   }
   for(let i=1;i<=m;i++) {
    for(let j=1;j<=n;j++) {
      if(s[i-1]==t[j-1]) {
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; //!注意加上之前累积的次数
      }else {
        dp[i][j] = dp[i-1][j];
      }
    }
   }
   return dp[m][n];
};
const s = "rabbbit", t = "rabbit";
console.log('不同的子序列',numDistinct(s,t)); //3